#include <iostream>
#include <assert.h>
#include <stack>
using namespace std;

template <typename T>
class Stack
{
public:
	bool stackIsLegal(char *q1, char *q2)
	{
		assert(q1);
		assert(q2);
		
		if (strlen(q1) != strlen(q2))
		{
			return false;
		}

		while (*q1 != '\0' && *q2 != '\0')
		{
			s.push(*q1++);
			if (s.top() != *q2)
			{
				s.push(*q1++);
			}
			while(!s.empty() && s.top() == *q2)
			{
				s.pop();
				q2++;
			}
		}
		return s.empty()? true:false;
	};

private:
	stack<T> s;
};

int main(int argc, char* argv[])
{
	Stack<char> s;
	char *q1 = "12345";
	char *q2 = "45321";
	bool ret = s.stackIsLegal(q1, q2);
	cout<<"ret:"<<boolalpha<<ret<<endl;
	system("pause");
	return 0;
}